import heapq
import math
import random
def solve(start, finish, heuristic):
    heap = []

    link = {} # parent node link
    h = {} # heuristic function cache
    g = {} # shortest path to a node

    g[start] = 0
    h[start] = 0
    link[start] = None
    numExpend = 0

    heapq.heappush(heap, (0, 0, start))
    # keep a count of the  number of steps, and avoid an infinite loop.
    for kk in xrange(1000000):
        print numExpend
        expend = False
        f, junk, current = heapq.heappop(heap)
        if current == finish:
            print "expended nodes number:", numExpend, "moves:", kk
            return g[current], kk

        moves = current.get_moves()
        distance = g[current]
        for mv in moves:
            if mv not in g or g[mv] > distance + 1:
                expend = True
                g[mv] = distance + 1
                if mv not in h:
                    h[mv] = heuristic(mv)
                link[mv] = current
                heapq.heappush(heap, (g[mv] + h[mv], -kk, mv))
        
        if expend == True:
            numExpend +=1

class Puzzle(object):
    def __init__(self, xs=None):
        n=3
        self.n = n
        self.n2 = n * n
        if xs is None:
            self.xs = [(x + 1) % self.n2 for x in xrange(self.n2)]
        else:
            self.xs = list(xs)
        self.hsh = None
        self.last_move = []

    def __hash__(self):
        if self.hsh is None:
            self.hsh = hash(tuple(self.xs))
        return self.hsh

    def __repr__(self):
        return "Puzzle(%d, %s)" % (self.n, self.xs)

    def show(self):
        ys = ["%2d" % x for x in self.xs]
        xs = [" ".join(ys[kk:kk+self.n]) for kk in xrange(0,self.n2, self.n)]
        return "\n".join(xs)

    def __eq__(self, other):
        return self.xs == other.xs

    def copy(self):
        return Puzzle(self.n, self.xs)

    def get_moves(self):
        # Find the 0 tile, and then generate moves
        tile0 = self.xs.index(0)
        def swap(i):
            #print 'swap',i
            j = tile0
            tmp = list(self.xs)
            last_move = tmp[i]
            tmp[i], tmp[j] = tmp[j], tmp[i]
            result = Puzzle(tmp)
            result.last_move = last_move
            return result

        if tile0 - self.n >= 0:   #down
            #print '111',tile0
            yield swap(tile0-self.n)
        if tile0 +self.n < self.n2: #up
            #print '222',tile0
            yield swap(tile0+self.n)
        if tile0 % self.n > 0:      #right
            #print '333',tile0
            yield swap(tile0-1)
        if tile0 % self.n < self.n-1:   #left
            #print '444',tile0
            yield swap(tile0+1)
                
def heuristic0(position):
   return 0

def heuristic1(position):
    n2 = position.n2    #9
    c = 0
    for kk in xrange(n2):
        if position.xs[kk] != kk+1:
            c += 1
    return c

def heuristic2(position):
    n = position.n
    def row(x): return x / n
    def col(x): return x % n
    score = 0
    for idx, x in enumerate(position.xs):
        if x == 0: continue
        ir,ic = row(idx), col(idx)
        xr,xc = row(x-1), col(x-1)
        score += abs(ir-xr) + abs(ic-xc)
    return score

s1=[6,4,7,8,5,0,3,2,1]
p = Puzzle(s1)
print p.show()
solve(p, Puzzle(), heuristic0)
solve(p, Puzzle(), heuristic1)
solve(p, Puzzle(), heuristic2)
